#!/usr/bin/env python

import sys
import copy
import cgi

from google.appengine.api import users
from google.appengine.ext import webapp
from google.appengine.ext.webapp.util import run_wsgi_app

#for brute force method
def same_row(i,j): return (i/9 == j/9)
def same_col(i,j): return (i-j) % 9 == 0
def same_square(i,j): return (i/27 == j/27 and i%9/3 == j%9/3)

def row(i):
   r=(i//9)*9
   return [ r, r+1, r+2, r+3, r+4, r+5, r+6, r+7, r+8 ]

def col(i):
   c=(i%9)
   return [c, c+9, c+18, c+27, c+36, c+45, c+54, c+63, c+72 ]

def square(i):
   s=(i//27)*27 + (((i%9)//3)*3)
   return [s, s+1, s+2, s+9, s+10, s+11, s+18, s+19, s+20 ]

class Board:
   possible = {}
   value    = {}

def isSolved(b):
   for i in range (81):
      if int(b.value[i]) == 0:
         return False
   return True

def printBoard(b):
#   for k in range (0, 81, 9):
#      print b.value[k+0], b.value[k+1], b.value[k+2], " | ",
#      print b.value[k+3], b.value[k+4], b.value[k+5], " | ",
#      print b.value[k+6], b.value[k+7], b.value[k+8]
#      if k==18 or k==45 or k==72:
#         print
  for k in range (0, 81, 9):
    self.response.out.write(puzzleAnswer[k+0:k+3] + ' | ' + puzzleAnswer[k+3:k+6] + ' | ' + puzzleAnswer[k+6:k+9]+'<br/>')
    if k is 18 or k is 45:
      self.response.out.write('---- + ---- + ----'+'<br/>')
    self.response.out.write('</body></html>')




#
# Find cases where only 1 cell could have a particular value
# It might have multiple possible values, but if it is the
# *only* one which could be "N", then it must be "N".
#
def setUniqueCells(b, cells):
   #print "setUniqueCells(", cells, ")"
   found_change = False
   all_possibles = ""
   for c in cells:
      if int(b.value[c]) == 0:
         #print "  ... setUniqueCells: From cell", c, ": adding the following to all_possibles: ", b.possible[c]
         all_possibles = all_possibles + b.possible[c]
   for v in "123456789":
      #print "  ... setUniqueCells(): all_possibles.count(", v, ") == ", all_possibles.count(v)
      if int(all_possibles.count(v)) == 1:
         for c in cells:
            #print "  ... possible[", c, "].count(", v, ") == ", b.possible[c].count(v), "  value[", c, "] == ", b.value[c]
            if int(b.possible[c].count(v) == 1) and int(b.value[c]) == 0:
               if setCell(b, c, v):
                  found_change = True
                  #print '  ... setUniqueCells: found a change for cell', c, ' of value ', v
   #print "  ... setUniqueCells, returning value: ", found_change
   return found_change

def setUniqueInBoard(b):
   change = True
   while change:
      change = False
      #print 'setUniqueInBoard: Checking all 9 rows      : change = ', change
      for k in range(0, 81, 9):
         if setUniqueCells(b, row(k)):
            change = True
      #print 'setUniqueInBoard: Checking all 9 columns   : change = ', change
      for k in range (9):
         if setUniqueCells(b, col(k)):
            change = True
      #print 'setUniqueInBoard: Checking all 9 squares   : change = ', change
      for k in range(0, 81,27):
         for j in range(k, k+9, 3):
            if setUniqueCells(b, square(j)):
               change = True

#
# Remove one possibility from the set of possible values for a cell
# If only 1 possibility remains, then SET this cell to that value
#
def markCell(b, position, val):
   #print "markCell(", position, ",", val, ")  value[position] == ", b.value[position], " possible[position] == ", b.possible[position]
   if int(b.value[position]) == 0:
      p = b.possible[position]
      i = p.find(val)
      if i == 0:
         p = p[1:]
      elif i != -1:
         p = p[:i] + p[i+1:]
      b.possible[position] = p
      #print "  ... marked ", val, " to produce possible[position] == ", b.possible[position]
      if int(b.value[position]) == 0 and int(len(p)) == 1:
         #print "  ... since only 1 value is possible, calling setCell(", position, ",", p[0], ")"
         if not setCell(b, position, p[0]):
            return False
   return True
   
def legalPosition(b, position, value):
   for x in row(position):
      if (x != position) and int(b.value[x]) == int(value):
         return False
   for x in col(position):
      if (x != position) and int(b.value[x]) == int(value):
         return False
   for x in square(position):
      if (x != position) and int(b.value[x]) == int(value):
         return False
   return True

#
# Set a cell to a particular value
# Because this is called by the brute force mechanism, it may be called with
# impossible situations (thus each value is tested for legality)
#
def setCell(b, position, newVal):
   #print "setCell(", position, ",", newVal, ")  value[position] == ", b.value[position], " possible[position] == ", b.possible[position]
   if int(b.value[position]) == 0:
      if not legalPosition(b, position, newVal):
         return False
      b.value[position] = newVal
      if int(newVal) != 0:
         b.possible[position] = newVal
         #print "  ... reset possible[", position, "] to ", b.possible[position]
         for x in row(position):
            if (x != position):
               #print "Marking position ", x, "to not have possibility", newVal, "from current set:", b.possible[x]
               if not markCell(b, x, newVal):
                  return False
         for x in col(position):
            if (x != position):
               #print "Marking position ", x, "to not have possibility", newVal, "from current set:", b.possible[x]
               if not markCell(b, x, newVal):
                  return False
         for x in square(position):
            if (x != position):
               #print "Marking position ", x, "to not have possibility", newVal, "from current set:", b.possible[x]
               if not markCell(b, x, newVal):
                  return False
   return True

#
# After solving as much as possible by simple deduction, use a
# brute-force recursive search to test what ever remains.  After
# each guess, however, reduce the search space using the existing
# set/mark functionality.  This should minimize the backtracking.
# This *could* be optimized by ordering the cells to search those
# with the fewest possiblities first, but it didn't seem necessary.
#
def bruteForce(b):
   #print "bruteForce: entering"
   for open_cell in range(81):
      if int(b.value[open_cell]) == 0:
         #print "bruteForce: looking at cell", open_cell, "with possible values", b.possible[open_cell]
         for i in b.possible[open_cell]:
            newBoard = Board()
            newBoard.value = copy.deepcopy(b.value)
            newBoard.possible = copy.deepcopy(b.possible)
            #print "bruteForce: Setting cell", open_cell, "to value", i
            if setCell(newBoard, open_cell, i):
               setUniqueInBoard(newBoard)
               if isSolved(newBoard):
                  #print "bruteForce: Found solution after set/mark/findUnique"
                  return newBoard
               newBoard = bruteForce(newBoard)
               if isSolved(newBoard):
                  #print "bruteForce: Found solution after recursive search"
                  return newBoard
   #print "bruteForce: Did not find solution"
   return b

def Solve(b, line):
   for i in range(81):
      b.possible[i] = "123456789"
      b.value[i] = '0'
   position=0
   for val in line:
      if val is not '0':
         setCell(b, position, val)
      position = position + 1
   #printBoard(b)
   #print '\n'
   #print '\n --- Done with first pass, printing current state\n'
   #print '\n --- Dump possible sets\n'
   #for i in range(81):
   #   print 'possible[', i, '] = ', b.possible[i]
   #print '\n --- setting unique cells\n'
   setUniqueInBoard(b)
   #printBoard(b)
   #print "\n"
   #print '\n --- dump possible sets\n'
   #for i in range(81):
   #   print 'possible[', i, '] = ', b.possible[i]
   solution = b
   if not isSolved(b):
      solution = bruteForce(b)
   return solution

class MainPage(webapp.RequestHandler):
  def get(self):
    self.response.out.write("""
    <html>
      <body>
        <form action="/sign" method="post">
          <div><textarea name="content" rows="10" cols="8"></textarea></div>
          <div><input type="submit" value="Solve"></div>
        </form>
      </body>
    </html>""")


class SolvedPage(webapp.RequestHandler):
  def post(self):
    puzzle = self.request.get('content')

    self.response.out.write('<html><body>Unsolved Puzzle:<p></p>')
    #cgi.escape is to make the html string safe to put on the side without
    #interpretation. Safety first. See here for a complete example:
    #https://developers.google.com/appengine/docs/python/gettingstarted/handlingforms  
    self.response.out.write(cgi.escape(puzzle))
    self.response.out.write('<p></p> Solved Puzzle:<p></p>')
    solver(puzzle)
    self.response.out.write(puzzleAnswer)
    self.response.out.write('<br></br>')

    b = Board()
    solution = Solve(b, sys.argv[1])
    if isSolved(solution):
      printBoard(solution)
    else:
       self.response.out.write("\nNo Solution!")
    #for k in range (0, 81, 9):
    #  self.response.out.write(puzzleAnswer[k+0:k+3] + ' | ' + puzzleAnswer[k+3:k+6] + ' | ' + puzzleAnswer[k+6:k+9]+'<br/>')
    #  if k is 18 or k is 45:
    #    self.response.out.write('---- + ---- + ----'+'<br/>')
    #self.response.out.write('</body></html>')


application = webapp.WSGIApplication(
                                     [('/', MainPage),
                                      ('/sign', SolvedPage)],
                                     debug=True)

def main():
    run_wsgi_app(application)

if __name__ == "__main__":
    main()
